/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  // 定义三个数组
  // 1.res 用于存放结果集
  // 2.stack 用于回溯存放的数值
  // 3.used 用于判断某个数值是否已经被存放过了
  let res = [],
    stack = [],
    used = new Array(nums.length).fill(false);
  // dfs 关键函数,回溯重点
  function dfs(depth) {
    // 如果说深度和nums的长度一样了
    // 说明当前的stack中的数值已经存完了nums里面的各个数值
    // 因此只需要装入即可
    if (depth == nums.length) {
      res.push([...stack]);
      return;
    }
    // 开始遍历
    for (let i = 0; i < nums.length; i++) {
      // 1.如果这个数已经被stack装入过，则跳过
      // 2.如果没有被stack装入过，则装入，同时设置used[i]为true
      if (!used[i]) {
        stack.push(nums[i]);
        used[i] = true;
        // 继续下一层级的查找
        dfs(depth + 1);
        // 回溯，将以前的值变回原样
        used[i] = false;
        stack.splice(stack.length - 1, 1);
      }
    }
  }
  dfs(0);
  return res;
};
let nums = [1, 2, 3];
console.log(permute(nums));
nums = [0, 1];
console.log(permute(nums));
nums = [1];
console.log(permute(nums));
